class Solution {
public:
    int dfs(int i){
        if(i<=1)    return 1;
        return dfs(i-1) + dfs(i-2);
    }
    int climbStairs(int n) {
        return dfs(n);
    }
};
